package cuiyt.algorithm.dfs;

import algorithm.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cyt
 * @create 2020-08-24 20:09
 */
public class T114 {
    /**
     * 给定一个二叉树，原地将它展开为一个单链表。
     * 例如，给定二叉树
     *
     *     1
     *    / \
     *   2   5
     *  / \   \
     * 3   4   6
     *
     * 1
     *  \
     *   2
     *    \
     *     3
     *      \
     *       4
     *        \
     *         5
     *          \
     *           6
     */

    /**
     * 可观察 展开后链表的顺序即为 先序遍历
     * 即： 采用先序遍历， 遍历二叉树， 在遍历的过程中改变节点的连接。
     * @param root
     */
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> nodes = new ArrayList<>();
        preorderTraversal(root,nodes);
        /**
         * nodes存放的所有的节点
         */
        int size = nodes.size();
        for(int i = 1; i<size; i++){
            /**
             * 一次得到两个节点然后设置节点关系
             */
            TreeNode prev = nodes.get(i - 1);
            TreeNode last = nodes.get(i);
            prev.left = null;
            prev.right = last;
        }
    }

    /**
     * 先序遍历得到所有的节点
     * @param root
     * @param list
     */
    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if(root!=null){
            list.add(root);
            preorderTraversal(root.left,list);
            preorderTraversal(root.right,list);
        }
    }

}





